#pragma once

#include <cstdio>
#include <iostream>
#include <mutex>
#include <random>
#include <vector>

#include "DataStream.h"
#include "SkipListDump.h"

namespace skip_list {
    // 跳表类
    template<typename K, typename V>
    class SkipList {
    public:
        explicit SkipList(size_t);

        ~SkipList();

        // 插入一个元素
        bool insert_element(K, V);
        // 查找元素,若找到则将对应的值通过引用参数返回，并返回true，否则返回false
        bool search_element(const K &, V *value);
        // 删除元素
        bool delete_element(const K &);
        // 设置元素(与insert_element区别是如果存在元素在改变其值)
        void set_element(K, V);
        // 将跳表结构转化为字符串形式（用于持久化）
        std::string dump_file();
        // 加载数据到跳表中
        void load_file(const std::string &);

        // 获取跳表当前元素个数
        [[nodiscard]] size_t size() const;

        // 展示跳表结构
        void display_list();

    private:
        // 获取随机层数，用于新节点插入
        size_t get_random_level();

        // 创建一个新节点
        Node<K, V> *create_node(K, V, size_t level);

        // 禁止拷贝构造函数和赋值运算符
        SkipList(const SkipList &) = delete;
        SkipList &operator=(const SkipList &) = delete;

        // 最大层数
        size_t max_level_;
        // 当前实际层数
        size_t skip_list_level_;
        // 头节点
        Node<K, V> *header_;
        // 当前元素个数
        size_t element_count_;
        // 互斥锁
        std::mutex mutex_;
    };
}// namespace skip_list

template<typename K, typename V>
skip_list::SkipList<K, V>::SkipList(const size_t max_level)
    : max_level_(max_level), skip_list_level_(0), element_count_(0) {
    K k;
    V v;
    this->header_ = new Node<K, V>(k, v, max_level);
}

template<typename K, typename V>
skip_list::SkipList<K, V>::~SkipList() {
    if (header_ != nullptr) {
        // 从第一个节点开始清理
        Node<K, V> *current = header_->forward_[0];
        delete header_;

        while (current != nullptr) {
            Node<K, V> *next = current->forward_[0];
            delete current;
            current = next;
        }
    }
}

template<typename K, typename V>
size_t skip_list::SkipList<K, V>::get_random_level() {

    // 在跳表中，一个节点的层级比前一个节点层级高的概率通常是一个固定的值，通常设为1/2
    static std::random_device rd;
    static std::mt19937 gen(rd());
    static std::uniform_int_distribution<> dis(0, 1);

    size_t k = 1;
    while (dis(gen)) {
        k++;
    }
    auto level = (k < max_level_) ? k : max_level_;
    return level;
}

template<typename K, typename V>
skip_list::Node<K, V> *skip_list::SkipList<K, V>::create_node(const K k, const V v, size_t level) {
    auto *node = new Node<K, V>(k, v, level);
    return node;
}


/*
                            +-------------+
                            |  insert 50  |
                            +-------------+
 level 4     +-->1+                                                      100
                  |
                  |                      insert +----+
 level 3         1+-------->10+---------------> | 50 |          70       100
                                                |    |
                                                |    |
 level 2         1          10         30       | 50 |          70       100
                                                |    |
                                                |    |
 level 1         1    4     10         30       | 50 |          70       100
                                                |    |
                                                |    |
 level 0         1    4   9 10         30   40  | 50 |  60      70       100
                                                +----+
 */

template<typename K, typename V>
bool skip_list::SkipList<K, V>::insert_element(const K key, const V value) {
    std::lock_guard<std::mutex> lock(mutex_);
    // 当前节点指针，初始化为头节点，遍历查找插入
    Node<K, V> *current = this->header_;

    // update数组，记录每一层要更新的节点指针
    std::vector<Node<K, V> *> update(skip_list_level_ + 1, nullptr);

    // 从最高层开始遍历
    for (int i = skip_list_level_; i >= 0; --i) {
        while (current->forward_[i] != nullptr &&
               current->forward_[i]->get_key() < key) {
            current = current->forward_[i];
        }
        update[i] = current;
    }
    current = current->forward_[0];

    // 判断元素是否已经存在
    if (current != nullptr && current->get_key() == key) {
        return false;
    }

    auto random_level = get_random_level();
    // 如果大于当前等级，则更新update数组中对应的中高层指针的头节点
    if (random_level > skip_list_level_) {
        for (int i = skip_list_level_ + 1; i <= random_level; ++i) {
            update.emplace_back(header_);
        }
        skip_list_level_ = random_level;
    }

    // 插入节点，从底层到顶层进行修改
    Node<K, V> *inserted_node = create_node(key, value, random_level);
    for (int i = 0; i <= random_level; ++i) {
        inserted_node->forward_[i] = update[i]->forward_[i];
        update[i]->forward_[i] = inserted_node;
    }
    ++element_count_;

    return true;
}

template<typename K, typename V>
bool skip_list::SkipList<K, V>::search_element(const K &key, V *value) {
    // 和插入元素思路差不多
    Node<K, V> *current = header_;

    for (int i = skip_list_level_; i >= 0; --i) {
        while (current->forward_[i] && current->forward_[i]->get_key() < key) {
            current = current->forward_[i];
        }
    }

    current = current->forward_[0];

    if (current != nullptr && current->get_key() == key) {
        *value = current->get_value();
        return true;
    }

    return false;
}

template<typename K, typename V>
bool skip_list::SkipList<K, V>::delete_element(const K &key) {
    std::lock_guard<std::mutex> lock(mutex_);
    Node<K, V> *current = this->header_;
    std::vector<Node<K, V> *> update(skip_list_level_ + 1, nullptr);

    for (int i = skip_list_level_; i >= 0; --i) {
        while (current->forward_[i] != nullptr && current->forward_[i]->get_key() < key) {
            current = current->forward_[i];
        }
        update[i] = current;
    }
    current = current->forward_[0];

    // 如果不存在则返回
    if (current == nullptr || current->get_key() != key) {
        return false;
    }


    for (int i = 0; i <= skip_list_level_; ++i) {
        if (update[i]->forward_[i] != current) {
            break;
        }
        update[i]->forward_[i] = current->forward_[i];
    }


    // 检查最高层是否已经没用节点了（即forward指针为空），没用则降低实际层数
    while (skip_list_level_ > 0 &&
           header_->forward_[skip_list_level_] == nullptr) {
        --skip_list_level_;
    }
    delete current;
    current = nullptr;
    --element_count_;
    return true;
}

template<typename K, typename V>
void skip_list::SkipList<K, V>::set_element(const K key, const V value) {
    V oldValue;
    if (search_element(key, &oldValue)) {
        delete_element(key);
    }
    insert_element(key, value);
}

template<typename K, typename V>
std::string skip_list::SkipList<K, V>::dump_file() {
    // 创建一个实际的对象而非unique_ptr
    SkipListDump<K, V> dumper;

    Node<K, V> *node = this->header_->forward_[0];

    // 循环遍历，插入到dumper中
    while (node != nullptr) {
        dumper.insert(*node);
        node = node->forward_[0];
    }

    DataStream data_stream;
    data_stream << dumper;

    std::string dump_str(data_stream.data(), data_stream.size());

    return dump_str;
}

template<typename K, typename V>
void skip_list::SkipList<K, V>::load_file(const std::string &dump_str) {
    if (dump_str.empty()) {
        return;
    }
    SkipListDump<K, V> dumper;
    DataStream data_stream;
    std::vector<char> dump_buffer(dump_str.c_str(), dump_str.c_str() + dump_str.size());
    data_stream.write(dump_buffer.data(), dump_buffer.size());
    data_stream >> dumper;

    for (int i = 0; i < dumper.key_dump_vt_.size(); ++i) {
        insert_element(dumper.key_dump_vt_[i], dumper.value_dump_vt_[i]);
    }
}

template<typename K, typename V>
size_t skip_list::SkipList<K, V>::size() const {
    return element_count_;
}

template<typename K, typename V>
void skip_list::SkipList<K, V>::display_list() {
    std::cout << "-*-*-*-*-*- Skip List -*-*-*-*-*-\n";
    for (int i = 0; i <= skip_list_level_; ++i) {
        Node<K, V> *node = this->header_->forward_[i];
        std::cout << "Level " << i << ": ";
        while (node != nullptr) {
            std::cout << node->get_key() << ": " << node->get_level() << "; ";
            node = node->forward_[i];
        }
    }
    std::cout << "\n";
}
